package _04_栈与队列;

import _01_第一季._00_公共接口.Queue;

/*
    循环队列
 */
public class ArrayLoopQueue<E> implements Queue<E> {
    private int size;
    private E[] elements;
    private int front; //指向队头元素
    private static final int DEFAULT_CAPACITY = 10;

    public ArrayLoopQueue(){
        elements = (E[]) new Object[DEFAULT_CAPACITY];
        front = 0;
        size = 0;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size==0;
    }

    //封装索引的方法
    private int index(int index){
        index += front;

        return index - (index >= elements.length  ? elements.length : 0);
    }

    //动态扩容
    private void ensureCapacity(int capacity) {
        int oldCapacity = elements.length; //原来的容量
        if(oldCapacity >= capacity) return; //如果原来的容量够，直接返回

        //新容量为原来的1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        E[] newElements = (E[]) new Object[newCapacity];
        for(int i=0;i<size;++i){
            newElements[i] = elements[index(i)]; //保证找到原数组front
        }
        //重新指向
        elements = newElements;
        front = 0; //改变队头指针的位置
    }

    @Override
    public void enQueue(E element) { //从队尾入队
        ensureCapacity(size + 1);
        //防止下标越界，所以控制下标，%上数组容量
        elements[index(size)] = element;
        size++;
    }

    @Override
    public E deQueue() {
        E ret = elements[front]; //队头元素
        elements[front] = null;
        front = index(1);
        size--;
        return ret;
    }

    @Override
    public E front() {
        return elements[front];
    }

    @Override
    public void clear() {
        for(int i=0;i<size;++i){
            elements[index(i)] = null;
        }
        front = 0;
        size = 0;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();

        sb.append("capacity= ").append(elements.length).append(" size= ")
                .append(size).append(" front= ").append(front)
                .append(", [");
        for(int i=0;i<elements.length;++i){
            if(i!=0){
                sb.append(',');
            }
            sb.append(elements[i]);
        }
        sb.append(']');

        return sb.toString();
    }
}
